{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum White Tiles Covered by a Carpet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #binary-search #prefix-sum #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #二分查找 #前缀和 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumWhiteTiles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #毯子覆盖的最多白色砖块数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组&nbsp;<code>tiles</code>&nbsp;，其中&nbsp;<code>tiles[i] = [l<sub>i</sub>, r<sub>i</sub>]</code>&nbsp;，表示所有在&nbsp;<code>l<sub>i</sub> &lt;= j &lt;= r<sub>i</sub></code>&nbsp;之间的每个瓷砖位置 <code>j</code>&nbsp;都被涂成了白色。</p>\n",
    "\n",
    "<p>同时给你一个整数&nbsp;<code>carpetLen</code>&nbsp;，表示可以放在&nbsp;<strong>任何位置</strong>&nbsp;的一块毯子的长度。</p>\n",
    "\n",
    "<p>请你返回使用这块毯子，<strong>最多</strong>&nbsp;可以盖住多少块瓷砖。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/25/example1drawio3.png\" style=\"width: 644px; height: 158px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10\n",
    "<b>输出：</b>9\n",
    "<b>解释：</b>将毯子从瓷砖 10 开始放置。\n",
    "总共覆盖 9 块瓷砖，所以返回 9 。\n",
    "注意可能有其他方案也可以覆盖 9 块瓷砖。\n",
    "可以看出，瓷砖无法覆盖超过 9 块瓷砖。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/24/example2drawio.png\" style=\"width: 231px; height: 168px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tiles = [[10,11],[1,1]], carpetLen = 2\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>将毯子从瓷砖 10 开始放置。\n",
    "总共覆盖 2 块瓷砖，所以我们返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= tiles.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>tiles[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= l<sub>i</sub> &lt;= r<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= carpetLen &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>tiles</code>&nbsp;互相 <strong>不会重叠</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-white-tiles-covered-by-a-carpet](https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-white-tiles-covered-by-a-carpet](https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,5],[10,11],[12,18],[20,25],[30,32]]\\n10', '[[10,11],[1,1]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, t: List[List[int]], carpetLen: int) -> int:\n",
    "\n",
    "        t.sort()\n",
    "        n=len(t)\n",
    "        left=0\n",
    "        pre=0\n",
    "        res=0\n",
    "        # 滑动窗口\n",
    "        for i,(l,r) in enumerate(t):\n",
    "            if r-l+1>=carpetLen:return carpetLen\n",
    "            while t[left][0]+carpetLen-1<r:\n",
    "                res=max(res,pre+max(0,t[left][0]+carpetLen-l))\n",
    "                pre-=t[left][1]-t[left][0]+1\n",
    "                left+=1\n",
    "            pre+=r-l+1\n",
    "            res=max(res,pre)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        n = len(tiles)\n",
    "        tot = min(tiles[0][-1] - tiles[0][0] + 1, carpetLen)\n",
    "        ans = tot\n",
    "        l = 0\n",
    "        for r in range(1,n):\n",
    "            tot += tiles[r][-1] - tiles[r][0] + 1\n",
    "            while l <= r and tiles[l][-1] < tiles[r][-1] - carpetLen + 1:\n",
    "                tot -= (tiles[l][-1] - tiles[l][0] + 1)\n",
    "                l += 1\n",
    "            if tiles[l][0] <= tiles[r][-1] - carpetLen + 1 <= tiles[l][-1]:\n",
    "                tot -= (tiles[r][-1] - carpetLen + 1 - tiles[l][0])\n",
    "                tiles[l][0] = tiles[r][-1] - carpetLen + 1\n",
    "            ans = max(ans,tot)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        n = len(tiles)\n",
    "        tot = 0\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        for r in range(n):\n",
    "            tot += tiles[r][-1] - tiles[r][0] + 1\n",
    "            # 毯子左端大于 tiles[l] 的右端，也就是说tiles[l]中的所有瓷砖都无法被覆盖\n",
    "            while l <= r and tiles[l][-1] < tiles[r][-1] - carpetLen + 1:\n",
    "                tot -= (tiles[l][-1] - tiles[l][0] + 1)\n",
    "                l += 1\n",
    "            # 毯子左端位于 tiles[l] 的中间，也就是说tiles[l]中的瓷砖只有一部分被覆盖\n",
    "            if tiles[l][0] <= tiles[r][-1] - carpetLen + 1 <= tiles[l][-1]:\n",
    "                tot -= (tiles[r][-1] - carpetLen + 1 - tiles[l][0])\n",
    "                # 更新tiles[l]的左端，因为已经减去了前半部分，不更新就可能存在重复计算了\n",
    "                tiles[l][0] = tiles[r][-1] - carpetLen + 1\n",
    "            ans = max(ans,tot)\n",
    "            # 最大也就是carpetLen\n",
    "            if ans == carpetLen:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()   # 按照起始位置排序\n",
    "        n = len(tiles)\n",
    "        res = 0   # 最多可以覆盖的瓷砖数量\n",
    "        cnt = 0   # 当前可以完全覆盖的连续瓷砖段的瓷砖数总和\n",
    "        r = 0   # 从左至右第一段无法完全覆盖的连续瓷砖的下标\n",
    "        # 枚举起始点对应连续瓷砖段的下标\n",
    "        for l in range(n):\n",
    "            if l:\n",
    "                cnt -= tiles[l-1][1] - tiles[l-1][0] + 1\n",
    "            while r < n and tiles[l][0] + carpetLen > tiles[r][1]:\n",
    "                cnt += tiles[r][1] - tiles[r][0] + 1\n",
    "                r += 1\n",
    "            if r == n:\n",
    "                # 此时无法通过右移增加覆盖瓷砖数，更新最大值并返回即可\n",
    "                res = max(res, cnt)\n",
    "                return res\n",
    "            extra = max(0, tiles[l][0] + carpetLen - tiles[r][0])   # 当前无法完全覆盖的连续瓷砖段的覆盖瓷砖数\n",
    "            res = max(res, cnt + extra)\n",
    "            print(r,cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()   # 按照左端点排序\n",
    "        n = len(tiles)\n",
    "        res = 0   # 最多可以覆盖的瓷砖数量\n",
    "        cnt = 0   # 当前可以完全覆盖的连续瓷砖段的瓷砖数总和\n",
    "        r = 0   # 从左至右第一段无法完全覆盖的连续瓷砖的下标\n",
    "        # 枚举起始点对应连续瓷砖段的下标\n",
    "        for l in range(n):\n",
    "            if l > 0:\n",
    "                cnt -= tiles[l-1][1] - tiles[l-1][0] + 1\n",
    "            while r < n and tiles[l][0] + carpetLen > tiles[r][1]:  # 能覆盖当前这段瓷砖区间\n",
    "                cnt += tiles[r][1] - tiles[r][0] + 1\n",
    "                r += 1\n",
    "            if r == n:\n",
    "                # 此时无法通过右移增加覆盖瓷砖数，更新最大值并返回即可\n",
    "                res = max(res, cnt)\n",
    "                return res\n",
    "            extra = max(0, tiles[l][0] + carpetLen - tiles[r][0])   # 当前无法完全覆盖的连续瓷砖段的覆盖瓷砖数\n",
    "            res = max(res, cnt + extra)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        # 先排序\n",
    "        tiles.sort(key=lambda t: t[0])  # \n",
    "        # 思考重点：变化量\n",
    "        # 结论：毯子的右端点和 tiles[i][1] 是对齐的\n",
    "        #      枚举 tiles[i][1]\n",
    "        # 毯子的左端点 tiles[i][1] - carpetLen + 1\n",
    "        left = 0\n",
    "        ans = cover = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            cl = tr - carpetLen + 1\n",
    "            while tiles[left][1] < cl:\n",
    "                # 移出整段瓷砖\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            if cl <= tiles[left][0]:\n",
    "                ans = max(ans, cover)\n",
    "            else:\n",
    "                ans = max(ans, cover - (cl - tiles[left][0]))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        left = cover = ret = 0\n",
    "        for start, end in tiles:\n",
    "            cover += end - start + 1\n",
    "            while tiles[left][1] < end - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ret = max(ret, cover - max(0, end - carpetLen + 1 - tiles[left][0]))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        cover = ans = 0\n",
    "        j = 0\n",
    "        n = len(tiles)\n",
    "        for i, (l, r) in enumerate(tiles):\n",
    "            while j < n and tiles[j][1] <= l + carpetLen - 1:\n",
    "                cover += tiles[j][1] - tiles[j][0] + 1\n",
    "                j += 1\n",
    "            if j < n:\n",
    "                ans = max(ans, cover + max(0, l + carpetLen - tiles[j][0]))\n",
    "            else:\n",
    "                ans = max(ans, cover)\n",
    "            cover -= tiles[i][1] - tiles[i][0] + 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        n = len(tiles)\n",
    "        tot = 0\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        for r in range(n):\n",
    "            tot += tiles[r][-1] - tiles[r][0] + 1\n",
    "            while l <= r and tiles[l][-1] < tiles[r][-1] - carpetLen + 1:\n",
    "                tot -= (tiles[l][-1] - tiles[l][0] + 1)\n",
    "                l += 1\n",
    "            if tiles[l][0] <= tiles[r][-1] - carpetLen + 1 <= tiles[l][-1]:\n",
    "                tot -= (tiles[r][-1] - carpetLen + 1 - tiles[l][0])\n",
    "                tiles[l][0] = tiles[r][-1] - carpetLen + 1\n",
    "            ans = max(ans,tot)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()   \n",
    "        ans = leftidx = acc = 0        \n",
    "        for a, b in tiles:\n",
    "            left = b - carpetLen # left + 1 为毯子左边界, 毯子右边界和 b 对齐\n",
    "            acc += b - a + 1 # 区间长度\n",
    "            x, y = tiles[leftidx]\n",
    "            while y <= left: # 小于左边界移出 边界为 left + 1\n",
    "                acc -= y - x + 1\n",
    "                leftidx += 1\n",
    "                x, y = tiles[leftidx]\n",
    "        \n",
    "            ans = max(ans, acc - max(left - x + 1, 0)); # 除去区间没有被毯子覆盖的部分，为负说明全包含了，当然不需要删除了。\n",
    "       \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        res = 0\n",
    "        left = 0 \n",
    "        tiles.sort()\n",
    "        right = 0\n",
    "        n = len(tiles)\n",
    "\n",
    "        cur = 0\n",
    "        while right < n and left < n:\n",
    "            l_s, l_e = tiles[left]\n",
    "            while right < n and tiles[right][1] - l_s + 1 <= carpetLen:\n",
    "                cur += tiles[right][1] - tiles[right][0] + 1\n",
    "                right += 1\n",
    "            extra = 0\n",
    "            if right < n and tiles[right][0] - l_s + 1 <= carpetLen:\n",
    "                extra = carpetLen - tiles[right][0] + l_s\n",
    "            res = max(res, cur + extra)\n",
    "\n",
    "            cur -= l_e - l_s + 1\n",
    "            left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        n = len(tiles)\n",
    "        left, right = 0, 0\n",
    "        tiles.sort(key = lambda x: x[0])\n",
    "        cover = 0\n",
    "        ans = 0\n",
    "        while right < n:\n",
    "            cover += tiles[right][1] - tiles[right][0] + 1\n",
    "            while tiles[right][1] - tiles[left][1] >= carpetLen:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(0, tiles[right][1] - tiles[left][0] + 1 - carpetLen))\n",
    "            right += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key=operator.itemgetter(0))\n",
    "        n = len(tiles)\n",
    "        ret = right = cnt = 0\n",
    "        for tl, tr in tiles:\n",
    "            while right < n and tiles[right][1] < tl + carpetLen - 1:\n",
    "                cnt += tiles[right][1] - tiles[right][0] + 1\n",
    "                right += 1\n",
    "\n",
    "            if right == n:\n",
    "                extra = 0\n",
    "            else:\n",
    "                extra = max(0, tl + carpetLen - tiles[right][0])\n",
    "            ret = max(ret, cnt + extra)\n",
    "            cnt -= tr - tl + 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        # 贪心地放毯子，将毯子的右端与一段地砖的右端对齐，然后枚举每一段地砖，都这样放地毯\n",
    "        # 用left指针计算左端的情况\n",
    "        tiles.sort()\n",
    "        ans = cover = left = 0\n",
    "        for tl,tr in tiles:\n",
    "            cover += (tr - tl + 1)\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= (tiles[left][1] - tiles[left][0] + 1)\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(0, tr-carpetLen+1 - tiles[left][0]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        res, total, n, j = 0, 0, len(tiles), 0\n",
    "        for i in range(n):\n",
    "            tail = tiles[i][0] + carpetLen - 1\n",
    "            while j < n and tiles[j][0] <= tail:\n",
    "                total += tiles[j][1] - tiles[j][0] + 1\n",
    "                j += 1\n",
    "            if tiles[j-1][1] > tail:\n",
    "                res = max(res, total - (tiles[j-1][1] - tail))\n",
    "            else:\n",
    "                res = max(res, total)\n",
    "            total -= tiles[i][1] - tiles[i][0] + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles = sorted(tiles, key=lambda x :x[0])\n",
    "        ans = 0\n",
    "        cover = 0\n",
    "        left = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        n = len(tiles)\n",
    "        tiles.sort()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        # print(tiles)\n",
    "        for i in range(n):\n",
    "            while j < n and tiles[j][1] <= tiles[i][0] + carpetLen - 1:\n",
    "                cnt += tiles[j][1] - tiles[j][0] + 1\n",
    "                j += 1\n",
    "            # print(i, j, tiles[j], cnt)\n",
    "            if j < n:\n",
    "                cnt += max(tiles[i][0] + carpetLen - tiles[j][0], 0)\n",
    "            # print(i, j, tiles[j], cnt)\n",
    "            ans = max(ans, cnt)\n",
    "            cnt -= tiles[i][1] - tiles[i][0] + 1\n",
    "            if j < n:\n",
    "                cnt -= max(tiles[i][0] + carpetLen - tiles[j][0], 0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key=lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))  # 0 表示毯子左端点不在瓷砖内的情况\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()   # 按照起始位置排序\n",
    "        n = len(tiles)\n",
    "        res = 0   # 最多可以覆盖的瓷砖数量\n",
    "        cnt = 0   # 当前可以完全覆盖的连续瓷砖段的瓷砖数总和\n",
    "        r = 0   # 从左至右第一段无法完全覆盖的连续瓷砖的下标\n",
    "        # 枚举起始点对应连续瓷砖段的下标\n",
    "        for l in range(n):\n",
    "            if l:\n",
    "                cnt -= tiles[l-1][1] - tiles[l-1][0] + 1\n",
    "            while r < n and tiles[l][0] + carpetLen > tiles[r][1]:\n",
    "                cnt += tiles[r][1] - tiles[r][0] + 1\n",
    "                r += 1\n",
    "            if r == n:\n",
    "                # 此时无法通过右移增加覆盖瓷砖数，更新最大值并返回即可\n",
    "                res = max(res, cnt)\n",
    "                return res\n",
    "            extra = max(0, tiles[l][0] + carpetLen - tiles[r][0])   # 当前无法完全覆盖的连续瓷砖段的覆盖瓷砖数\n",
    "            res = max(res, cnt + extra)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles, carpetLen):\n",
    "        tiles.sort()\n",
    "        n = len(tiles)\n",
    "        l = 0\n",
    "        r = 0\n",
    "        total = 0\n",
    "        ans = 0\n",
    "        while l <= r and r < n:\n",
    "            leftBoundary = tiles[l][0]\n",
    "            rightBoundary = leftBoundary + carpetLen - 1\n",
    "            #未覆盖完\n",
    "            if tiles[r][1] <= rightBoundary:\n",
    "                total += tiles[r][1] - tiles[r][0] + 1\n",
    "                r += 1\n",
    "                ans = max(total, ans)\n",
    "            else:\n",
    "                #覆盖部分\n",
    "                if rightBoundary >= tiles[r][0]:\n",
    "                    ans = max(total + rightBoundary - tiles[r][0] + 1, ans)\n",
    "                #调整到下一个区间开头\n",
    "                total -= tiles[l][1] - tiles[l][0] + 1\n",
    "                l += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles = sorted(tiles,key=lambda x:x[0])\n",
    "        l,r = 0,0 # 表示此时目标覆盖的左右边界的区间索引\n",
    "        sumD = 0\n",
    "        res = 0\n",
    "        n = len(tiles)\n",
    "        while l <= r and r < n:\n",
    "            left,right = tiles[l][0],tiles[l][0]+carpetLen-1 # 此时覆盖的左右边界\n",
    "            if tiles[r][1] < right: # 能够覆盖的最大个数\n",
    "                sumD += tiles[r][1] - tiles[r][0] + 1\n",
    "                res = max(res,sumD)\n",
    "                r += 1\n",
    "            else: # tiles[r][1] >= right:\n",
    "                if tiles[r][0] <= right:\n",
    "                    res = max(res,sumD+right-tiles[r][0]+1)\n",
    "                sumD -= tiles[l][1] - tiles[l][0] + 1\n",
    "                l += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int: \n",
    "        n = len(tiles)\n",
    "        tiles.sort()\n",
    "        preSum = [0]*(n+1)\n",
    "        for i,(l,r) in enumerate(tiles):\n",
    "            preSum[i+1] = preSum[i]+r-l+1 # preSum[i+1]表示0...i块砖的贡献\n",
    "        res = 0\n",
    "        for i,(l,r) in enumerate(tiles):\n",
    "            ## 从这块砖最左边放，考察 l+carpetLen能放到第几块砖\n",
    "            j = bisect_right(tiles,l+carpetLen-1,key=lambda p: p[1])\n",
    "            if j==n:\n",
    "                cur = preSum[j]-preSum[i] ## [i,...,j]这些砖\n",
    "            else:\n",
    "                cur = preSum[j]-preSum[i]+max(0,l+carpetLen-tiles[j][0])\n",
    "            res = max(res,cur)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key=lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))  # 0 表示毯子左端点不在瓷砖内的情况\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, t: List[List[int]], ct: int) -> int:\n",
    "        t.sort()\n",
    "        left=0\n",
    "        res=0\n",
    "        s=0\n",
    "        for l,r in t:\n",
    "            if r-l+1>=ct:return ct\n",
    "            while t[left][0]+ct-1<r:\n",
    "                res=max(res,s+  max(0,t[left][0]+ct-l))\n",
    "                s-=t[left][1]-t[left][0]+1\n",
    "                left+=1\n",
    "            \n",
    "            s+=r-l+1\n",
    "            res=max(res,s)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, t: List[List[int]], ct: int) -> int:\n",
    "        t.sort()\n",
    "        left=0\n",
    "        res=0\n",
    "        s=0\n",
    "        for l,r in t:\n",
    "            # if r-l+1>=ct:return ct\n",
    "            while left<len(t) and  t[left][0]+ct-1<r:\n",
    "                res=max(res,s+  max(0,t[left][0]+ct-l))\n",
    "                s-=t[left][1]-t[left][0]+1\n",
    "                left+=1\n",
    "            \n",
    "            s+=r-l+1\n",
    "            res=max(res,s)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        a, b = [], []\n",
    "        for s, e in tiles:\n",
    "            a.append(s)\n",
    "            b.append(e - s + 1)\n",
    "        pre = [0]\n",
    "        n = len(a)\n",
    "        for i in range(n):\n",
    "            pre.append(pre[-1] + b[i])\n",
    "        ans = 0\n",
    "        index = 0\n",
    "        for i in range(n):\n",
    "            s, e = a[i], a[i] + carpetLen - 1\n",
    "            while index < n and a[index] <= e:\n",
    "                index += 1\n",
    "            t1 = pre[index - 1] - pre[i]\n",
    "            t2 = min(b[index - 1], e - a[index - 1] + 1)\n",
    "            ans = max(ans, t1 + t2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        n=len(tiles)\n",
    "        tiles.sort(key= lambda x:x[0])\n",
    "        part=[0]\n",
    "        cur=0\n",
    "        for i in range(n):\n",
    "            cur+=tiles[i][1]-tiles[i][0]+1\n",
    "            part.append(cur)\n",
    "        check=[x for x,y in tiles]\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            target=tiles[i][0]+carpetLen-1\n",
    "            j=bisect_right(check,target)\n",
    "            total=part[j-1]-part[i]\n",
    "            total+=min(target-check[j-1]+1,tiles[j-1][1]-tiles[j-1][0]+1)\n",
    "            ans=max(ans,total)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()   # 按照起始位置排序\n",
    "        n = len(tiles)\n",
    "        res = 0   # 最多可以覆盖的瓷砖数量\n",
    "        cnt = 0   # 当前可以完全覆盖的连续瓷砖段的瓷砖数总和\n",
    "        r = 0   # 从左至右第一段无法完全覆盖的连续瓷砖的下标\n",
    "        # 枚举起始点对应连续瓷砖段的下标\n",
    "        for l in range(n):\n",
    "            if l:\n",
    "                cnt -= tiles[l-1][1] - tiles[l-1][0] + 1\n",
    "            while r < n and tiles[l][0] + carpetLen > tiles[r][1]:\n",
    "                cnt += tiles[r][1] - tiles[r][0] + 1\n",
    "                r += 1\n",
    "            if r == n:\n",
    "                # 此时无法通过右移增加覆盖瓷砖数，更新最大值并返回即可\n",
    "                res = max(res, cnt)\n",
    "                return res\n",
    "            extra = max(0, tiles[l][0] + carpetLen - tiles[r][0])   # 当前无法完全覆盖的连续瓷砖段的覆盖瓷砖数\n",
    "            res = max(res, cnt + extra)\n",
    "            print(r,cnt,extra,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        for a,b in tiles:\n",
    "            if b-a+1 >= carpetLen:return carpetLen\n",
    "        tiles.sort()\n",
    "        carpetLen -= 1\n",
    "        ce = tiles[0][0] + carpetLen\n",
    "        temp = 0\n",
    "        res = 0\n",
    "        pos = len(tiles)\n",
    "        for idx,(s,e) in enumerate(tiles):\n",
    "            if e > ce:\n",
    "                pos = idx\n",
    "                break\n",
    "            else:\n",
    "                temp += e-s+1\n",
    "        if pos < len(tiles) and tiles[pos][0] <= ce:\n",
    "            temp += ce - tiles[pos][0] + 1\n",
    "        res = temp\n",
    "        if pos < len(tiles) and tiles[pos][0] <= ce:\n",
    "            temp -= ce - tiles[pos][0] + 1\n",
    "        pre = 0\n",
    "        while pos < len(tiles):\n",
    "            ce += tiles[pre+1][0]-tiles[pre][0]\n",
    "            temp -= tiles[pre][1]-tiles[pre][0]+1\n",
    "            pre += 1\n",
    "            while pos < len(tiles) and tiles[pos][1] <= ce:\n",
    "                temp += tiles[pos][1]-tiles[pos][0]+1\n",
    "                pos += 1\n",
    "            if pos < len(tiles) and tiles[pos][0] <= ce:\n",
    "                temp += ce - tiles[pos][0] + 1 \n",
    "            res = max(res,temp)\n",
    "            if pos < len(tiles) and tiles[pos][0] <= ce:\n",
    "                temp -= ce - tiles[pos][0] + 1 \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        sorted_tiles = sorted(tiles, key=lambda d:d[0])\n",
    "        n = len(sorted_tiles)\n",
    "        end_pos = sorted_tiles[0][0] + carpetLen - 1\n",
    "\n",
    "        p = 0\n",
    "        now = sorted_tiles[0][1] - sorted_tiles[0][0] + 1\n",
    "        while p + 1 < n and sorted_tiles[p + 1][0] <= end_pos:\n",
    "            p += 1\n",
    "            now += sorted_tiles[p][1] - sorted_tiles[p][0] + 1\n",
    "        \n",
    "        if end_pos >= sorted_tiles[p][1]:\n",
    "            res = now\n",
    "        else:\n",
    "            res = now - (sorted_tiles[p][1] - sorted_tiles[p][0] + 1) + (end_pos - sorted_tiles[p][0] + 1)\n",
    "        \n",
    "        for head_index in range(1, n):\n",
    "            end_pos = sorted_tiles[head_index][0] + carpetLen - 1\n",
    "            now -= sorted_tiles[head_index - 1][1] - sorted_tiles[head_index - 1][0] + 1\n",
    "            while p + 1 < n and sorted_tiles[p + 1][0] <= end_pos:\n",
    "                p += 1\n",
    "                now += sorted_tiles[p][1] - sorted_tiles[p][0] + 1\n",
    "            \n",
    "            if end_pos >= sorted_tiles[p][1]:\n",
    "                res = max(res, now)\n",
    "            else:\n",
    "                res = max(res, now - (sorted_tiles[p][1] - sorted_tiles[p][0] + 1) + (end_pos - sorted_tiles[p][0] + 1))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        s = 0\n",
    "        for l,r in tiles:\n",
    "            q.append((l,r))\n",
    "            s += r-l+1\n",
    "            while r - q[0][0] + 1 > carpetLen:\n",
    "                x,y = q.popleft()\n",
    "                s -= y-x+1\n",
    "                p = r-carpetLen + 1\n",
    "                if p <= y:\n",
    "                    q.appendleft((p,y))\n",
    "                    s += y-p+1\n",
    "            ans = max(ans,s)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key = lambda x: x[0])\n",
    "        leftIndex = 0\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        print(tiles)\n",
    "        for a, b in tiles:\n",
    "            count += b - a + 1\n",
    "            while b - tiles[leftIndex][1] + 1 > carpetLen:\n",
    "                count -= tiles[leftIndex][1] - tiles[leftIndex][0] + 1\n",
    "                leftIndex += 1\n",
    "            if b - carpetLen < tiles[leftIndex][0]:\n",
    "                ans = max(ans, count)\n",
    "            else:\n",
    "                ans = max(ans, count - ((b - carpetLen) - tiles[leftIndex][0] + 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        def delta_len(x):\n",
    "            return x[1] - x[0] + 1\n",
    "        tiles.sort()\n",
    "        i, j, n = 0, 0, len(tiles)\n",
    "        ans, last_ans, last_pos = 0, 0, 0\n",
    "        while i < n:\n",
    "            if delta_len(tiles[i]) >= carpetLen:\n",
    "                ans = carpetLen\n",
    "                break\n",
    "            else:\n",
    "                end_pos = tiles[i][0] + carpetLen - 1\n",
    "                if i > 0:\n",
    "                    last_ans = last_ans - delta_len(tiles[i - 1])\n",
    "                while j < n and tiles[j][0] <= end_pos:\n",
    "                    if last_pos != 0:\n",
    "                        if tiles[j][1] <= end_pos:\n",
    "                            last_ans += tiles[j][1] - last_pos\n",
    "                            last_pos = 0\n",
    "                            j += 1\n",
    "                        else:\n",
    "                            last_ans += end_pos - last_pos\n",
    "                            last_pos = end_pos\n",
    "                            break\n",
    "                    else:\n",
    "                        if tiles[j][1] <= end_pos:\n",
    "                            last_ans += delta_len(tiles[j])\n",
    "                            j += 1\n",
    "                        else:\n",
    "                            last_ans += end_pos - tiles[j][0] + 1\n",
    "                            last_pos = end_pos\n",
    "                            break\n",
    "                ans = max(last_ans, ans)\n",
    "                i += 1      \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        # 将tiles 按左端点排序，枚举坛子的摆放位置， 计算能覆盖瓷砖数\n",
    "        # tiles.sort(key = lambda x: x[0])\n",
    "        # ans = cover = left = 0\n",
    "\n",
    "        # for tl, tr in tiles:\n",
    "        #     cover += tr - tl + 1 # 坛子长度\n",
    "        #     while tiles[left][1] < tr - carpetLen + 1: # \n",
    "        #         cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "        #         left += 1\n",
    "        #     ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0)) # 0 表示毯子左端点不在瓷砖内\n",
    "        # return ans\n",
    "\n",
    "        tiles.sort(key = lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        l = 0\n",
    "        n = len(tiles)\n",
    "        gap = [0] * (n + 1)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(1, n):\n",
    "            if tiles[i - 1][1] - tiles[i - 1][0] + 1 >= carpetLen:\n",
    "                return carpetLen\n",
    "            gap[i] = gap[i - 1] + tiles[i][0] - tiles[i - 1][1] - 1\n",
    "            f[i] = f[i - 1] + tiles[i - 1][1] - tiles[i - 1][0] + 1\n",
    "        f[n] = f[n - 1] + tiles[n - 1][1] - tiles[n - 1][0] + 1\n",
    "        # print(tiles)\n",
    "        # print(gap)\n",
    "        # print(f)\n",
    "        res = min(carpetLen, tiles[0][1] - tiles[0][0] + 1)\n",
    "        for i in range(1, n):\n",
    "            while tiles[i][1] - tiles[l][1] >= carpetLen:\n",
    "                l += 1\n",
    "            total = tiles[i][1] - tiles[l][0] + 1\n",
    "            if total < carpetLen:\n",
    "                res = max(res, f[i + 1] - f[l])\n",
    "            else:\n",
    "                res = max(res, carpetLen - gap[i] + gap[l])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        n = len(tiles)\n",
    "        left, right = 0, 0\n",
    "        tiles.sort(key = lambda x: x[0])\n",
    "        cover = 0\n",
    "        ans = 0\n",
    "        while left < n:\n",
    "            while right < n and tiles[right][1] - tiles[left][0] + 1<carpetLen:\n",
    "                cover += tiles[right][1] - tiles[right][0] + 1\n",
    "                right += 1\n",
    "            if right < n and tiles[right][0] - tiles[left][0] < carpetLen:\n",
    "                ans = max(ans, cover + carpetLen - tiles[right][0] + tiles[left][0])\n",
    "            else:\n",
    "                ans = max(ans, cover)\n",
    "            cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "            left += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        # 先排序\n",
    "        tiles.sort(key=lambda t: t[0])\n",
    "        # 思考重点：变化量\n",
    "        # 结论：毯子的右端点和 tiles[i][1] 是对齐的\n",
    "        #      枚举 tiles[i][1]\n",
    "        # 毯子的左端点 tiles[i][1] - carpetLen + 1\n",
    "        left = 0\n",
    "        ans = cover = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            cl = tr - carpetLen + 1\n",
    "            while tiles[left][1] < cl:\n",
    "                # 移出整段瓷砖\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            # if cl <= tiles[left][0]:\n",
    "            #     ans = max(ans, cover)\n",
    "            # else:\n",
    "            ans = max(ans, cover - max(cl - tiles[left][0], 0))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: list[list[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key = lambda x:x[0])\n",
    "        cover = left = ans =0\n",
    "        for tl,tr in tiles:\n",
    "            cover += tr -tl+1\n",
    "            while tiles[left][1]<tr-carpetLen+1:\n",
    "                cover-=tiles[left][1]-tiles[left][0]+1\n",
    "                left+=1\n",
    "            ans = max(ans,cover-max(tr-carpetLen+1-tiles[left][0],0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "瓷砖按左端点排序，然后枚举毯子位置\n",
    "'''\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key=lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))  # 0 表示毯子左端点不在瓷砖内的情况\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        cover = ans = 0\n",
    "        j = 0\n",
    "        n = len(tiles)\n",
    "        for i, (l, r) in enumerate(tiles):\n",
    "            if i > 0:\n",
    "                cover -= tiles[i - 1][1] - tiles[i - 1][0] + 1\n",
    "            while j < n and tiles[j][1] <= l + carpetLen - 1:\n",
    "                cover += tiles[j][1] - tiles[j][0] + 1\n",
    "                j += 1\n",
    "            # print(j, cover, (l + carpetLen - tiles[j][0]) if j < n and l + carpetLen >= tiles[j][0] else 0)\n",
    "            ans = max(ans, cover + ((l + carpetLen - tiles[j][0]) if j < n and l + carpetLen - 1 >= tiles[j][0] else 0))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles = sorted(tiles)\n",
    "        left = 0\n",
    "        cover = 0\n",
    "        ans = 0\n",
    "        for tl, tr in tiles:\n",
    "            # 当前管道有几个\n",
    "            cover += tr - tl + 1\n",
    "            # 毯子右移时左边的右端点无法覆盖了，把覆盖的数减去，左指针右移\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            # 能覆盖了就更新最大值\n",
    "            # 0 表示毯子左端点不在瓷砖内的情况\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        cv = [0]\n",
    "        acc = 0\n",
    "        tiles.sort()\n",
    "        for x,y in tiles:\n",
    "            acc += y - x + 1\n",
    "            cv.append(acc)\n",
    "            \n",
    "        ans = 1\n",
    "        #print(cv)\n",
    "        for i,(x,y) in enumerate(tiles):\n",
    "            end = x + carpetLen - 1\n",
    "            pos = bisect_right(tiles, end, key = lambda x : x[0]) - 1\n",
    "            #print(x,y, pos , cv[pos] - cv[i] + min(end, tiles[pos][1]) - tiles[pos][0])\n",
    "            ans = max(cv[pos] - cv[i] + min(end, tiles[pos][1]) - tiles[pos][0] + 1, ans)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        n = len(tiles)\n",
    "        tiles.sort(key = lambda x : x[0])\n",
    "\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        cover = 0\n",
    "\n",
    "        for tl,tr in tiles:\n",
    "            cover += tr - tl+1\n",
    "            while tiles[left][1] < tr - carpetLen +1:\n",
    "                cover -= tiles[left][1]-tiles[left][0]+1\n",
    "                left+=1\n",
    "            ans = max(ans, cover-max(tr-carpetLen+1-tiles[left][0],0))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        # 先排序\n",
    "        tiles.sort()  # key=lambda t: t[0]\n",
    "        # 思考重点：变化量\n",
    "        # 结论：毯子的右端点和 tiles[i][1] 是对齐的\n",
    "        #      枚举 tiles[i][1]\n",
    "        # 毯子的左端点 tiles[i][1] - carpetLen + 1\n",
    "        left = 0\n",
    "        ans = cover = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            cl = tr - carpetLen + 1\n",
    "            while tiles[left][1] < cl:\n",
    "                # 移出整段瓷砖\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            if cl <= tiles[left][0]:\n",
    "                ans = max(ans, cover)\n",
    "            else:\n",
    "                ans = max(ans, cover - (cl - tiles[left][0]))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key=lambda x:x[0])\n",
    "        left = 0\n",
    "        ans = count= 0\n",
    "        for i,tile  in enumerate(tiles):\n",
    "            # 添加当前的这一段瓷砖\n",
    "            count +=tile[1] -tile[0]+1\n",
    "            while  tiles[left][1] < tile[1] - carpetLen + 1:\n",
    "                count -= tiles[left][1]-tiles[left][0]+1\n",
    "                left +=1\n",
    "            # 要减去非瓷砖\n",
    "            ans = max(ans,count-max(tile[1]-carpetLen+1-tiles[left][0],0))\n",
    "        return ans\n",
    "\n",
    "        # tiles.sort(key=lambda x: x[0])\n",
    "        # ans = cover = left = 0\n",
    "        # for tl, tr in tiles:\n",
    "        #     cover += tr - tl + 1\n",
    "        #     while tiles[left][1] < tr - carpetLen + 1:\n",
    "        #         cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "        #         left += 1\n",
    "        #     ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))  # 0 表示毯子左端点不在瓷砖内的情况\n",
    "        # return ans\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key=lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))  # 0 表示毯子左端点不在瓷砖内的情况\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key=lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        # 应该是一定放置在开头的位置，这样子无论如何都是最优的选择\n",
    "        mx = 0\n",
    "        tiles.sort()\n",
    "        presum = list(accumulate([r-l+1 for l, r in tiles], initial=0))\n",
    "        left = [l for l, r in tiles]\n",
    "        right = [r for l, r in tiles]\n",
    "        \n",
    "        for i ,l in enumerate(left):\n",
    "            r = l + carpetLen-1\n",
    "            j = bisect_left(right, r)\n",
    "            if j == len(right):\n",
    "                j = j-1\n",
    "                v = presum[j+1] - presum[i]\n",
    "            else:\n",
    "                v = presum[j] - presum[i]\n",
    "                lj, rj = tiles[j]\n",
    "                if r >= lj:\n",
    "                    v += r - lj + 1\n",
    "            \n",
    "            mx = max(mx, v)\n",
    "        \n",
    "        return mx\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key = lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl,tr in tiles:\n",
    "            cover += tr-tl+1\n",
    "            while tiles[left][1] < tr-carpetLen+1:\n",
    "                cover -= tiles[left][1]-tiles[left][0]+1\n",
    "                left += 1\n",
    "            ans = max(ans,cover-max(tr-carpetLen+1-tiles[left][0],0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key = lambda x: x[0])\n",
    "        ans =  left = count=0\n",
    "        \n",
    "        for tl,tr  in tiles:\n",
    "            count += tr- tl +1\n",
    "            while  tr - tiles[left][1] +1 >  carpetLen:\n",
    "                count -= tiles[left][1] - tiles[left][0] +1  \n",
    "                left +=1\n",
    "            ans  = max(ans,count - max(tr-carpetLen+1-tiles[left][0],0))\n",
    "        return ans\n",
    "            \n",
    "      \n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: list[list[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key = lambda x:x[0])\n",
    "        cover = left = ans =0\n",
    "        for tl,tr in tiles:\n",
    "            cover += tr -tl+1\n",
    "            while tiles[left][1]<tr-carpetLen+1:\n",
    "                cover-=tiles[left][1]-tiles[left][0]+1\n",
    "                left+=1\n",
    "            ans = max(ans,cover-max(tr-carpetLen+1-tiles[left][0],0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        r = 0\n",
    "        arr = [x[0] for x in tiles]\n",
    "        pre_sum = [0]*(len(tiles)+1)\n",
    "        base = tiles[0][0]\n",
    "        #前i块有多少\n",
    "        cnt = 1\n",
    "    \n",
    "        for x,y in tiles:\n",
    "            pre_sum[cnt] = pre_sum[cnt-1]+y-x+1\n",
    "            cnt+=1\n",
    "        print(pre_sum)\n",
    "        print(arr)\n",
    "        for i in range(1,len(tiles)+1):\n",
    "            right = tiles[i-1][1]\n",
    "            if ans == carpetLen:\n",
    "                return carpetLen\n",
    "            if right-tiles[i-1][0]+1>=carpetLen:\n",
    "                return carpetLen\n",
    "            if right-base+1<=carpetLen:\n",
    "                ans = max(ans,pre_sum[i])\n",
    "            else:\n",
    "                left = right-carpetLen\n",
    "                j = bisect_right(arr,left)\n",
    "                if j>0:\n",
    "                    prey = tiles[j-1][1]\n",
    "                    ans = max(ans,pre_sum[i]-pre_sum[j]+(prey-left if prey > left else 0))\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        n=len(tiles)\n",
    "        tiles.sort(key= lambda x:x[0])\n",
    "        part=[0]\n",
    "        cur=0\n",
    "        for i in range(n):\n",
    "            cur+=tiles[i][1]-tiles[i][0]+1\n",
    "            part.append(cur)\n",
    "        check=[x for x,y in tiles]\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            target=tiles[i][0]+carpetLen-1\n",
    "            j=bisect_right(check,target)\n",
    "            total=part[j-1]-part[i]\n",
    "            total+=min(target-check[j-1]+1,tiles[j-1][1]-tiles[j-1][0]+1)\n",
    "            ans=max(ans,total)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key = lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl,tr in tiles:\n",
    "            cover += tr-tl+1\n",
    "            while tiles[left][1] < tr-carpetLen+1:\n",
    "                cover -= tiles[left][1]-tiles[left][0]+1\n",
    "                left += 1\n",
    "            ans = max(ans,cover-max(0,tr-carpetLen+1-tiles[left][0]))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key=lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        # 将tiles 按左端点排序，枚举坛子的摆放位置， 计算能覆盖瓷砖数\n",
    "        tiles.sort(key = lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1 # 坛子长度\n",
    "            while tiles[left][1] < tr - carpetLen + 1: # \n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0)) # 0 表示毯子左端点不在瓷砖内\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key=lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))  # 0 表示毯子左端点不在瓷砖内的情况\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        # tiles.sort(key=lambda x:x[0])\n",
    "        # left = 0\n",
    "        # ans = count= 0\n",
    "        # for i,tile  in enumerate(tiles):\n",
    "        #     # 添加当前的这一段瓷砖\n",
    "        #     count +=tile[1] -tile[0]+1\n",
    "        #     while tile[1] - tiles[left][0] +1 >carpetLen:\n",
    "        #         count -= tiles[left][1]-tiles[left][0]+1\n",
    "        #         left +=1\n",
    "        #     # 要减去非瓷砖\n",
    "        #     ans = max(ans,count-max(tile[1]-carpetLen+1-tiles[left][0],0))\n",
    "        # return ans\n",
    "\n",
    "        tiles.sort(key=lambda x: x[0])\n",
    "        ans = cover = left = 0\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))  # 0 表示毯子左端点不在瓷砖内的情况\n",
    "        return ans\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        n=len(tiles)\n",
    "        tiles.sort()\n",
    "        pre=[0]\n",
    "        for i,v in enumerate(tiles):\n",
    "            pre.append(pre[-1]+v[1]-v[0]+1)\n",
    "            if v[1]-v[0]+1>=carpetLen:return carpetLen\n",
    "        res=0\n",
    "        for i,v in enumerate(tiles):\n",
    "            l,r=v\n",
    "            left,right=i,n-1\n",
    "            while left<right:\n",
    "                mid=left+right+1>>1\n",
    "                if tiles[mid][0]>l+carpetLen-1:\n",
    "                    right=mid-1\n",
    "                else:\n",
    "                    left=mid\n",
    "            maxDis=l+carpetLen-1\n",
    "            if maxDis>=tiles[right][1]:\n",
    "                res=max(res,pre[right+1]-pre[i])\n",
    "            else:\n",
    "                print(i,v,left,tiles[right])\n",
    "                ans=pre[left]-pre[i]+l+carpetLen-tiles[left][0]\n",
    "                res=max(res,ans)\n",
    "        return res\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key=lambda x:x[0])\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        cover = 0\n",
    "\n",
    "        for tl, tr in tiles:\n",
    "            cover += tr - tl + 1\n",
    "            while tiles[left][1] < tr - carpetLen + 1:\n",
    "                cover -= tiles[left][1] - tiles[left][0] + 1\n",
    "                left += 1\n",
    "            ans = max(ans, cover - max(tr - carpetLen + 1 - tiles[left][0], 0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        a, b = [], []\n",
    "        for s, e in tiles:\n",
    "            a.append(s)\n",
    "            b.append(e - s + 1)\n",
    "        pre = [0]\n",
    "        n = len(a)\n",
    "        for i in range(n):\n",
    "            pre.append(pre[-1] + b[i])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s, e = a[i], a[i] + carpetLen - 1\n",
    "            index = bisect.bisect_right(a, e)\n",
    "            t1 = pre[index - 1] - pre[i]\n",
    "            t2 = min(b[index - 1], e - a[index - 1] + 1)\n",
    "            ans = max(ans, t1 + t2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "\n",
    "        tiles.sort(key = lambda x:(x[0], x[1]))\n",
    "\n",
    "        left = 0\n",
    "        right = carpetLen\n",
    "\n",
    "        presum = [0] * len(tiles)\n",
    "        presum[0] = tiles[0][1] - tiles[0][0] + 1\n",
    "\n",
    "        for i in range(1, len(presum)):\n",
    "            presum[i] = presum[i - 1] + tiles[i][1] - tiles[i][0] + 1\n",
    "        def cc(l, r, i):\n",
    "            left = 0\n",
    "            right = len(tiles) - 1\n",
    "\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "\n",
    "                if tiles[mid][0] > r:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid\n",
    "\n",
    "            ll,rr = tiles[left]\n",
    "\n",
    "            if rr <= r:\n",
    "                return presum[left] - (presum[i - 1] if i - 1 >= 0 else 0)\n",
    "            else:\n",
    "                p1 = r - ll + 1\n",
    "\n",
    "                p2 = (presum[left - 1] if left - 1 >= 0 else 0) - (presum[i - 1] if i - 1 >= 0 else 0)        \n",
    "                return p1 + p2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(tiles)):\n",
    "            leftSide, rightSide = tiles[i]\n",
    "\n",
    "            l = leftSide\n",
    "            r = l + carpetLen - 1\n",
    "\n",
    "\n",
    "            ans = max(ans, cc(l, r, i))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        deltas = [r - l + 1 for l, r in tiles]\n",
    "        ans, i, j, n = 0, 0, 0, len(tiles)\n",
    "        last_ans, last_pos = 0, 0\n",
    "        while i < n:\n",
    "            l, r = tiles[i]\n",
    "            d = deltas[i]\n",
    "            if d >= carpetLen:\n",
    "                ans = carpetLen\n",
    "                break\n",
    "            else:\n",
    "                end_pos = l + carpetLen - 1\n",
    "                if i > 0:\n",
    "                    last_ans = last_ans - deltas[i - 1]\n",
    "                while j < n and tiles[j][0] <= end_pos:\n",
    "                    if last_pos != 0:\n",
    "                        if tiles[j][1] <= end_pos:\n",
    "                            last_ans += tiles[j][1] - last_pos\n",
    "                            last_pos = 0\n",
    "                            j += 1\n",
    "                        else:\n",
    "                            last_ans += end_pos - last_pos\n",
    "                            last_pos = end_pos\n",
    "                            break\n",
    "                    else:\n",
    "                        if tiles[j][1] <= end_pos:\n",
    "                            last_ans += deltas[j]\n",
    "                            j += 1\n",
    "                        else:\n",
    "                            last_ans += end_pos - tiles[j][0] + 1\n",
    "                            last_pos = end_pos\n",
    "                            break\n",
    "                ans = max(last_ans, ans)\n",
    "                print(l, d, ans, last_pos, j)\n",
    "                i += 1      \n",
    "        print(deltas)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort()\n",
    "        a, b = [], []\n",
    "        for s, e in tiles:\n",
    "            a.append(s)\n",
    "            b.append(e - s + 1)\n",
    "        pre = [0]\n",
    "        n = len(a)\n",
    "        for i in range(n):\n",
    "            pre.append(pre[-1] + b[i])\n",
    "        ans = 0\n",
    "        index = 0\n",
    "        for i in range(n):\n",
    "            s, e = a[i], a[i] + carpetLen - 1\n",
    "            while index < n and a[index] <= e:\n",
    "                index += 1\n",
    "            t1 = pre[index - 1] - pre[i]\n",
    "            t2 = min(b[index - 1], e - a[index - 1] + 1)\n",
    "            ans = max(ans, t1 + t2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:\n",
    "        tiles.sort(key = lambda x:x[0])\n",
    "        n = len(tiles)\n",
    "\n",
    "        l, r = 0, 0\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        while r < n:\n",
    "            st, ed = tiles[r]\n",
    "            cur += ed - st + 1\n",
    "            while ed - tiles[l][1] > carpetLen:\n",
    "                st1, ed1 = tiles[l]\n",
    "                cur -= ed1 - st1 + 1\n",
    "                l += 1\n",
    "\n",
    "            cannot_cover = 0\n",
    "            if tiles[l][0] <= ed - carpetLen <= tiles[l][1]:\n",
    "                cannot_cover = ed - carpetLen - tiles[l][0] + 1\n",
    "\n",
    "            ans = max(ans, cur - cannot_cover)\n",
    "            r += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
